{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delquote(s):\n",
    "    s=s.strip()\n",
    "    n=len(s)\n",
    "    if n>=2 and s[0]==s[-1]=='\\'':\n",
    "        s=s[1:n-1]\n",
    "        res=[]\n",
    "        i=0\n",
    "        while i<n-2:\n",
    "            if s[i]=='\\\\':\n",
    "                if i!=n-3:\n",
    "                    res.append(s[i+1])\n",
    "                    i+=2\n",
    "            else:\n",
    "                res.append(s[i])\n",
    "                i+=1\n",
    "        return ''.join(res)\n",
    "    else:\n",
    "        return s\n",
    "\n",
    "def addquote(s):\n",
    "    res=['\\'']\n",
    "    for c in s:\n",
    "        if c in ['\\\\','\\'']:\n",
    "            res.append('\\\\'+c)\n",
    "        else:\n",
    "            res.append(c)\n",
    "    return ''.join(res)+'\\''\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [],
   "source": [
    "TOKEN_TRUE=('True',0)\n",
    "TOKEN_FALSE=('False', 0)\n",
    "AS_FALSE=[('False', 0), ('', 0), []]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 解析单个单次 N'...' 或 '...' 或 ...\n",
    "def parse_word(word):\n",
    "    word=word.strip()\n",
    "    n=len(word)\n",
    "    if n<=1:\n",
    "        return word,0\n",
    "    if word[-1]=='\\'':\n",
    "        i=word.index('\\'')\n",
    "        return delquote(word[i:n]),int(word[:i]) if i>0 else 1\n",
    "    else:\n",
    "        return word,0\n",
    "\n",
    "# 解析单一表达式到解析树\n",
    "def parse(in_str):\n",
    "    res=[[]]\n",
    "    last=i=0\n",
    "    while i<len(in_str):\n",
    "        c=in_str[i]\n",
    "        if c=='\\'':\n",
    "            j=i+1\n",
    "            bslash=0\n",
    "            while j<len(in_str):\n",
    "                d=in_str[j]\n",
    "                if d=='\\\\':\n",
    "                    bslash+=1\n",
    "                elif d=='\\'' and bslash%2==0:\n",
    "                    break\n",
    "                else:\n",
    "                    bslash=0\n",
    "                j+=1\n",
    "            res[-1].append(parse_word(in_str[last:j+1]))\n",
    "            i=j\n",
    "            last=i=i+1\n",
    "\n",
    "        elif c=='(':\n",
    "            res.append([])\n",
    "            last=i=i+1\n",
    "\n",
    "        elif c==')':\n",
    "            t=res.pop()\n",
    "            if last<i:\n",
    "                t.append(parse_word(in_str[last:i]))\n",
    "            res[-1].append(t)\n",
    "            last=i=i+1\n",
    "\n",
    "        elif c==' ':\n",
    "            if last<i:\n",
    "                res[-1].append(parse_word(in_str[last:i]))\n",
    "            last=i=i+1\n",
    "\n",
    "        else:\n",
    "            i+=1\n",
    "    else:\n",
    "        if last<i:\n",
    "            res[-1].append(parse_word(in_str[last:i]))\n",
    "    if res[0]:\n",
    "        return res[0][0]\n",
    "    else:\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 无函数调用，仅仅减小引用次数\n",
    "def eval0(tree, keys=[], vals=[]):\n",
    "    if type(tree)==tuple:\n",
    "        w,q=tree\n",
    "        if q>1:\n",
    "            return (w,q-1)\n",
    "        elif q==1:\n",
    "            return parse(w)\n",
    "        else:\n",
    "            if w in keys:\n",
    "                return vals[keys.index(w)]\n",
    "            else:\n",
    "                return (w,0)\n",
    "    elif type(tree)==list:\n",
    "        res=[]\n",
    "        for item in tree:\n",
    "            res.append(eval0(item,keys,vals))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 有函数调用，无尾递归\n",
    "# 函数形式((参数列表) 单个函数体表达式)\n",
    "def eval1(tree, keys=[], vals=[]):\n",
    "    if type(tree)==tuple:\n",
    "        w,q=tree\n",
    "        if q>1:\n",
    "            return (w,q-1)\n",
    "        elif q==1:\n",
    "            return parse(w)\n",
    "        else:\n",
    "            if w in keys:\n",
    "                return vals[keys.index(w)]\n",
    "            else:\n",
    "                return (w,0)\n",
    "    elif type(tree)==list:\n",
    "        res=[]\n",
    "        for item in tree:\n",
    "            res.append(eval1(item,keys,vals))\n",
    "        if len(res)>=1 and type(res[0])==list:\n",
    "            func=res[0]\n",
    "            if len(func)==2 and type(func[0])==list:\n",
    "                argus=func[0]\n",
    "                argvs=res[1:]\n",
    "                n=len(argus)\n",
    "                if n==len(argvs):\n",
    "                    for u,v in zip(argus,argvs):\n",
    "                        keys.insert(0,u[0])\n",
    "                        vals.insert(0,v)\n",
    "                    res=eval1(func[1],keys,vals)\n",
    "                    for i in range(n):\n",
    "                        keys.pop(0)\n",
    "                        vals.pop(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 有函数调用，有尾递归\n",
    "# 函数形式((参数列表) 单个函数体表达式)\n",
    "def eval2(tree, keys=[], vals=[]):\n",
    "    if type(tree)==tuple:\n",
    "        w,q=tree\n",
    "        if q>1:\n",
    "            return (w,q-1)\n",
    "        elif q==1:\n",
    "            return parse(w)\n",
    "        else:\n",
    "            if w in keys:\n",
    "                return vals[keys.index(w)]\n",
    "            else:\n",
    "                return (w,0)\n",
    "    elif type(tree)==list:\n",
    "        lkeys=len(keys)\n",
    "        res=[]\n",
    "        for item in tree:\n",
    "            res.append(eval2(item,keys,vals))\n",
    "            while len(keys)>lkeys:\n",
    "                keys.pop(0);vals.pop(0)\n",
    "        if len(res)>=1 and type(res[0])==list:\n",
    "            func=res[0]\n",
    "            if len(func)==2 and type(func[0])==list:\n",
    "                argus=func[0]\n",
    "                argvs=res[1:]\n",
    "                n=len(argus)\n",
    "                if n==len(argvs):\n",
    "                    for u,v in zip(argus,argvs):\n",
    "                        keys.insert(0,u[0]);vals.insert(0,v)\n",
    "                    return eval2(func[1],keys,vals)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "def interfuncs(name):\n",
    "    def evalargvs(argvs,keys,vals):\n",
    "        res=[]\n",
    "        lkeys=len(keys)\n",
    "        for item in argvs:\n",
    "            res.append(eval3(item,keys,vals))\n",
    "            while len(keys)>lkeys:\n",
    "                keys.pop(0);vals.pop(0)\n",
    "        return res\n",
    "\n",
    "    def echo(argvs,keys,vals):\n",
    "        return argvs[0] if len(argvs)==1 else argvs\n",
    "\n",
    "    def eval(argvs,keys,vals):\n",
    "        res=evalargvs(argvs, keys, vals)\n",
    "        res=evalargvs(res, keys, vals)\n",
    "        return res[0] if len(res)==1 else res\n",
    "\n",
    "    def quot(argvs,keys,vals):\n",
    "        argvs=evalargvs(argvs, keys, vals)\n",
    "        def solve(item):\n",
    "            return (item[0],item[1]+1) if type(item)==tuple else [solve(t) for t in item]\n",
    "        res=[]\n",
    "        for t in argvs:\n",
    "            res.append(solve(t))\n",
    "        return res[0] if len(res)==1 else res\n",
    "    \n",
    "    def equal(argvs,keys,vals):\n",
    "        res=evalargvs(argvs, keys, vals)\n",
    "        if len(res)==0:\n",
    "            return []\n",
    "        a=res[0]\n",
    "        for item in res:\n",
    "            if a!=item:\n",
    "                return TOKEN_FALSE\n",
    "        return TOKEN_TRUE\n",
    "    \n",
    "    def add(argvs,keys,vals):\n",
    "        res=evalargvs(argvs, keys, vals)\n",
    "        if len(res)==0:\n",
    "            return []\n",
    "        a=0\n",
    "        for item in res:\n",
    "            if type(item)==tuple and item[0].isdigit():\n",
    "                a+=int(item[0])\n",
    "            else:\n",
    "                return []\n",
    "        return (str(a),0)\n",
    "\n",
    "    def sub(argvs,keys,vals):\n",
    "        res=evalargvs(argvs, keys, vals)\n",
    "        if len(res)==0:\n",
    "            return []\n",
    "        nums=[]\n",
    "        for item in res:\n",
    "            if type(item)==tuple and item[0].isdigit():\n",
    "                nums.append(int(item[0]))\n",
    "            else:\n",
    "                return []\n",
    "        return (str(nums[0]-sum(nums[1:]) if len(nums)>1 else -nums[0]),0)\n",
    "\n",
    "    def notfunc(argvs,keys,vals):\n",
    "        argvs=evalargvs(argvs, keys, vals)\n",
    "        if len(argvs)==0:\n",
    "            return []\n",
    "        res=[]\n",
    "        for item in argvs:\n",
    "            if item in AS_FALSE:\n",
    "                res.append(TOKEN_TRUE)\n",
    "            else:\n",
    "                res.append(TOKEN_FALSE)\n",
    "        return res[0] if len(res)==1 else res\n",
    "\n",
    "    def andfunc(argvs,keys,vals):\n",
    "        argvs=evalargvs(argvs, keys, vals)\n",
    "        if len(argvs)==0:\n",
    "            return []\n",
    "        for item in argvs:\n",
    "            if item in AS_FALSE:\n",
    "                return item\n",
    "        return argvs[-1]\n",
    "\n",
    "    def orfunc(argvs,keys,vals):\n",
    "        argvs=evalargvs(argvs, keys, vals)\n",
    "        if len(argvs)==0:\n",
    "            return []\n",
    "        for item in argvs:\n",
    "            if item not in AS_FALSE:\n",
    "                return item\n",
    "        return argvs[-1]\n",
    "\n",
    "    def iffunc(argvs,keys,vals):\n",
    "        if len(argvs)==3:\n",
    "            lkeys=len(keys)\n",
    "            condition=eval3(argvs[0],keys,vals)\n",
    "            while len(keys)>lkeys:\n",
    "                keys.pop(0);vals.pop(0)\n",
    "            if condition in AS_FALSE:\n",
    "                return eval3(argvs[2],keys,vals)\n",
    "            else:\n",
    "                return eval3(argvs[1],keys,vals)\n",
    "        return []\n",
    "\n",
    "    def car(argvs,keys,vals):\n",
    "        argvs=evalargvs(argvs, keys, vals)\n",
    "        res=[]\n",
    "        for item in argvs:\n",
    "            if type(item)==list and len(item)>=1:\n",
    "                res.append(item[0])\n",
    "            else:\n",
    "                return []\n",
    "        return res[0] if len(res)==1 else res\n",
    "    \n",
    "    def cdr(argvs,keys,vals):\n",
    "        argvs=evalargvs(argvs, keys, vals)\n",
    "        res=[]\n",
    "        for item in argvs:\n",
    "            if type(item)==list and len(item)>=1:\n",
    "                res.append(item[1:])\n",
    "            else:\n",
    "                return []\n",
    "        return res[0] if len(res)==1 else res\n",
    "    \n",
    "    def let(argvs,keys,vals):\n",
    "        if len(argvs)==0:\n",
    "            return argvs\n",
    "        elif len(argvs)==1:\n",
    "            return eval3(argvs[0],keys,vals)\n",
    "        varpairs, body=evalargvs(argvs[:-1], keys, vals),argvs[-1]\n",
    "        for item in varpairs:\n",
    "            if type(item)==list and len(item)==2 and type(item[0])==tuple:\n",
    "                keys.insert(0,item[0][0])\n",
    "                vals.insert(0,item[1])\n",
    "        return eval3(body,keys,vals)\n",
    "    \n",
    "    \n",
    "    d={\n",
    "        'echo':echo,\n",
    "        'eval':eval,\n",
    "        'quot':quot,\n",
    "        '=':equal,\n",
    "        '+':add,\n",
    "        '-':sub,\n",
    "        'not':notfunc,\n",
    "        'or':orfunc,\n",
    "        'and':andfunc,\n",
    "        'if':iffunc,\n",
    "        'car':car,\n",
    "        'cdr':cdr,\n",
    "        'let':let,\n",
    "\n",
    "    }\n",
    "    if name in d:\n",
    "        return d[name]\n",
    "    else:\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 有函数调用，有尾递归，有内置函数\n",
    "# 用户函数形式((参数列表) 单个函数体表达式)\n",
    "# 内置函数参数为未求值的参数列表\n",
    "def eval3(tree, keys=[], vals=[]):\n",
    "    if type(tree)==tuple:\n",
    "        w,q=tree\n",
    "        if q>1:\n",
    "            return (w,q-1)\n",
    "        elif q==1:\n",
    "            return parse(w)\n",
    "        else:\n",
    "            if w in keys:\n",
    "                return vals[keys.index(w)]\n",
    "            else:\n",
    "                return (w,0)\n",
    "    elif type(tree)==list:\n",
    "        # 内置函数\n",
    "        if len(tree)>0 and type(tree[0])==tuple and tree[0][1]==0:\n",
    "            func=interfuncs(tree[0][0])\n",
    "            if func is not None:\n",
    "                return func(tree[1:], keys, vals)\n",
    "        # 求解所有项\n",
    "        res=[]\n",
    "        lkeys=len(keys)\n",
    "        for item in tree:\n",
    "            res.append(eval3(item,keys,vals))\n",
    "            while len(keys)>lkeys:\n",
    "                keys.pop(0);vals.pop(0)\n",
    "        # 用户函数\n",
    "        if len(res)>=1:\n",
    "            if type(res[0])==list:\n",
    "                func=res[0]\n",
    "                if len(func)==2 and type(func[0])==list:\n",
    "                    argus=func[0]\n",
    "                    argvs=res[1:]\n",
    "                    n=len(argus)\n",
    "                    if n==len(argvs):\n",
    "                        for u,v in zip(argus,argvs):\n",
    "                            keys.insert(0,u[0]);vals.insert(0,v)\n",
    "                        return eval3(func[1],keys,vals)\n",
    "        return res\n",
    "    else:\n",
    "        return TOKEN_FALSE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print0(tree):\n",
    "    if type(tree)==tuple:\n",
    "        w,q=tree\n",
    "        if q==0:\n",
    "            return w\n",
    "        elif q==1:\n",
    "            return addquote(w)\n",
    "        else:\n",
    "            return str(q)+addquote(w)\n",
    "    elif type(tree)==list:\n",
    "        res=[print0(t) for t in tree]\n",
    "        return '('+' '.join(res)+')'\n",
    "    else:\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(let (f ((n) (if (or (= n 1) (= n 2)) 1 (+ (f (- n 1)) (f (- n 2)))))) (f 10))\t55                            \n",
      "(let (f ((n a b) (if (= n 1) a (f (- n 1) b (+ a b))))) (f 100 1 1))\t354224848179261915075         \n"
     ]
    }
   ],
   "source": [
    "test_list=[\n",
    "    # \"((('a') 'a') 'c')\",\n",
    "    # \"('((a) a)' 'c')\",\n",
    "    # \"((('a' 'b') ('b' 'a')) 'c' 'd')\",\n",
    "    # \"('(\\\\'\\\\' ())' )\",\n",
    "    # \"(echo 'a' 'b')\",\n",
    "    # \"(eval 2'a')\",\n",
    "    # \"(quot ('' 'c' 'd'))\",\n",
    "    # \"(= 'a' 'a')\",\n",
    "    # \"(= () ())\",\n",
    "    # \"(if (= 'a' 'a') (echo yes) (echo no))\",\n",
    "    # \"(let (a 1) (b 2) (eval (() 'a' 'b')))\",\n",
    "    # \"(let (f '((x) (+ x x))') (f '2'))\"\n",
    "    \"(let (f '((n) (if (or (= n 1) (= n 2)) 1 (+ (f (- n 1)) (f (- n 2)) ) ) )' ) (f '10'))\",\n",
    "    \"(let (f '((n a b) (if (= n 1)  a (f (- n 1) b (+ a b))) )' ) (f '100' '1' '1'))\",\n",
    "\n",
    "]\n",
    "for s in test_list:\n",
    "    tree=parse(s)\n",
    "    # print(\"%-30s\"%s+'\\t'+\"%-30s\"%print0(eval0(tree,[],[]))+'\\t'+\"%-30s\"%print0(eval3(tree,[],[])))\n",
    "    print(\"%-30s\"%print0(eval0(tree,[],[]))+'\\t'+\"%-30s\"%print0(eval3(tree,[],[])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "49f30f08d477d7e971cce0721b46a8098f01c02c1d83915ee06530c213be12e0"
  },
  "kernelspec": {
   "display_name": "Python 3.7.0 ('base')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
